home *** CD-ROM | disk | FTP | other *** search
/ Belgian Amiga Club - ADF Collection / BS1 part 34.zip / BS1 part 34 / FredFish PD 306.adf / Tree / sort.c < prev    next >
C/C++ Source or Header  |  1990-01-11  |  5KB  |  214 lines
  1. /*
  2.  *   A quicksort routine; nothing special.  Only works on machines
  3.  *   which store the most significant byte of a longword in the
  4.  *   first byte, and so on.
  5.  */
  6. #include "stdio.h"
  7. char **lineptrs ;
  8. long numlines ;
  9. long lineptrsize ;
  10. char inbuf[255] ;
  11. char **ssmin[25], **ssmax[25] ;
  12. int stval ;
  13. void *lmalloc() ;
  14. #define MEMCHUNK 4096
  15. #define swap(a, b) {t= a;a= b;b= t;}
  16. char *tbuf ;
  17. int bytesleft ;
  18. int reverse ;
  19. char *saveit(s)
  20. register char *s ;
  21. {
  22.    int len = (strlen(s) + (2*sizeof(long)-1)) & ~(sizeof(long)-1) ;
  23.    register char *p ;
  24.  
  25.    if (len > bytesleft) {
  26.       tbuf = (char *)lmalloc((long)MEMCHUNK) ;
  27.       if (tbuf == NULL)
  28.          error("! couldn't allocate memory") ;
  29.       bytesleft = MEMCHUNK ;
  30.    }
  31.    p = tbuf ;
  32.    while (*p++ = *s++) ;
  33.    s = tbuf ;
  34.    tbuf += len ;
  35.    while (p < tbuf)
  36.       *p++ = 0 ;
  37.    bytesleft -= len ;
  38.    return(s) ;
  39. }
  40. long strlcmp(a, b)
  41. register long *a, *b ;
  42. {
  43.    while (*a == *b && *a) {
  44.       a++ ;
  45.       b++ ;
  46.    }
  47.    return(*b - *a) ;
  48. }
  49. error(s)
  50. char *s ;
  51. {
  52.    fputs("sort: ", stdout) ;
  53.    puts(s) ;
  54.    if (*s == '!')
  55.       exit(1) ;
  56. }
  57. getlines() {
  58.    register int c ;
  59.    register char *p ;
  60.    register long i ;
  61.    char **olineptrs ;
  62.  
  63.    lineptrsize = 0 ;
  64.    numlines = 0 ;
  65.    while (1) {
  66.       p = inbuf ;
  67.       while ((c=getchar())!=EOF && c != 10) {
  68.          *p++ = c ;
  69.          if (p > inbuf + 250)
  70.             error("! input line too long") ;
  71.       }
  72.       *p = 0 ;
  73.       if (c==EOF && p==inbuf)
  74.          break ;
  75.       p = saveit(inbuf) ;
  76.       if (numlines >= lineptrsize) {
  77.          olineptrs = lineptrs ;
  78.          lineptrsize = lineptrsize + (MEMCHUNK/sizeof(char *)) ;
  79.          lineptrs = (char **)lmalloc((long)sizeof(char *)*lineptrsize) ;
  80.          if (lineptrs == NULL)
  81.             error("! couldn't allocate memory") ;
  82.          for (i=0; i<lineptrsize-MEMCHUNK/sizeof(char *); i++)
  83.             lineptrs[i] = olineptrs[i] ;
  84.          free(olineptrs) ;
  85.       }
  86.       lineptrs[numlines++] = p ;
  87.    }
  88. }
  89. sortlines() {
  90.    register char **i, **j ;
  91.    register char *medp ;
  92.    char **min, **max, **med ;
  93.    register char *t ;
  94.  
  95.    stval = 0 ;
  96.    min = lineptrs ;
  97.    max = lineptrs + numlines - 1 ;
  98.    while (1) {
  99.       if (max < min + 3) {
  100.          if (max > min) {
  101.             if (strlcmp(*max, *min)<0)
  102.                swap(*max, *min) ;
  103.             if (max == min + 2) {
  104.                if (strlcmp(*(min+1), *min)<0)
  105.                   swap(*(min+1),*min) ;
  106.                if (strlcmp(*max, *(min+1))<0)
  107.                   swap(*max,*(min+1)) ;
  108.             }
  109.          }
  110.          if (stval > 0) {
  111.             stval-- ;
  112.             min = ssmin[stval] ;
  113.             max = ssmax[stval] ;
  114.          } else
  115.             break ;
  116.       } else {
  117.          med = min + (max - min) / 2 ;
  118.          if (strlcmp(*max, *min)<0)
  119.             swap(*max, *min) ;
  120.          if (strlcmp(*med, *min)<0)
  121.             swap(*med, *min) ;
  122.          if (strlcmp(*max, *med)<0)
  123.             swap(*max, *med) ;
  124.          i = min + 1 ;
  125.          j = max - 1 ;
  126.          medp = *med ;
  127.          while (1) {
  128.             if (strlcmp(medp, *i)>=0) {
  129.                i++ ;
  130.                if (i>j)
  131.                   break ;
  132.             } else
  133.                goto checkj ;
  134.             if (strlcmp(*j, medp)>=0) {
  135.                j-- ;
  136.                if (i>j)
  137.                   break ;
  138.             } else
  139.                goto checki ;
  140.             continue ;
  141. checki:
  142.             while (strlcmp(medp, *i)>=0 && i<=j)
  143.                i++ ;
  144.             goto over ;
  145. checkj:
  146.             while (strlcmp(*j, medp)>=0 && i<=j)
  147.                j-- ;
  148. over:
  149.             if (i < j) {
  150.                swap(*i, *j)
  151.                i++ ;
  152.                j-- ;
  153.                if (i>j)
  154.                   break ;
  155.             } else
  156.                break ;
  157.          }
  158.          if (j-min > max-i) {
  159.             ssmin[stval] = min ;
  160.             ssmax[stval] = j ;
  161.             stval++ ;
  162.             min = i ;
  163.          } else {
  164.             ssmin[stval] = i ;
  165.             ssmax[stval] = max ;
  166.             stval++ ;
  167.             max = j ;
  168.          }
  169.       }
  170.    }
  171. }
  172. putlines() {
  173.    register long i ;
  174.  
  175.    if (reverse)
  176.       for (i=0; i<numlines; i++)
  177.          puts(lineptrs[i]) ;
  178.    else
  179.       for (i=numlines-1; i>=0; i--)
  180.          puts(lineptrs[i]) ;
  181. }
  182. main(argc, argv)
  183. int argc ;
  184. char *argv[] ;
  185. {
  186.    while (argc > 1 && argv[1][0]=='-') {
  187.       argc-- ;
  188.       argv++ ;
  189.       switch(argv[0][1]) {
  190. case 'r' : reverse = 1 ;
  191.         break ;
  192. default :  break ;
  193.       }
  194.    }
  195.    if (argc > 1) {
  196.       argc-- ;
  197.       argv++ ;
  198.       if (freopen(argv[0], "r", stdin) == NULL)
  199.          error("! couldn't open input file") ;
  200.    }
  201.    if (argc > 1) {
  202.       argc-- ;
  203.       argv++ ;
  204.       if (freopen(argv[0], "w", stdout) == NULL)
  205.          error("! couldn't open output file") ;
  206.    }
  207.    getlines() ;
  208.    if (numlines > 1)
  209.       sortlines() ;
  210.    putlines() ;
  211.    fclose(stdout) ;
  212. }
  213. _wb_parse() {}
  214.